// 时间复杂度： O(n*logn)
// 空间复杂度: O(1)

const { LinkedList, ListNode } = require('../1. 链表基础/1. 建立线性链表')

function quickSort(left, right) {
    if (left === right || left.next === right) {
        return left
    }
    let pi = partition(left, right)
    quickSort(left, pi)
    quickSort(pi.next, right)
    return left
}

function partition(left, right) {
    // 左闭右开，区间没有元素或者只有一个元素，直接返回第一个节点
    if (left === right || left.next === right) {
        return left
    }

    // 选择头节点为基准节点
    let pivot = left.val
    // node_i和node_j双指针，保证node_i之前的节点值都小于基准节点值，node_i和node_j之间的节点值都大于
    // 等于基准节点值
    let node_i = left
    let node_j = left.next
    while (node_j !== right) {
        // 发现一个小于基准值的元素
        if (node_j.val < pivot) {
            // 因为node_i之前节点都小于基准值，所以先将node_i向右移动一位（此时node_i节点值大于等于基准节点值）
            node_i = node_i.next;
            // 将小于基准值的元素node_j与当前node_i换位，换位后可以保证node_i之前的节点都小于基准节点值 
            [node_i.val, node_j.val] = [node_j.val, node_i.val]
        }
        node_j = node_j.next
    }
    // 把基准节点放到正确位置上
    [node_i.val, left.val] = [left.val, node_i.val]
    return node_i
}

const linkList = new LinkedList([2, 5, 1, 6, 3, 4])
let res = quickSort(linkList.head, null)
console.log(res)